#include <new>
#include <string.h>
#include <assert.h>

#include "net_context.h"
#include "num_pool.h"

using namespace usnet;

NumPool::~NumPool()
{
    if (cur_tab_size_ != MIN_TAB_SIZE) {
        delete[] num_tab_.cur_tab_;
        num_tab_.cur_tab_ = num_tab_.min_tab_;
    }
}

NumPool::NumPool(uint32_t nbits):
    max_num_ { (1u << nbits) - 1u },
    max_tab_size_ { 1u << (nbits - TAB_UNI_BITS) }
{
    assert((MIN_NUM_BITS <= nbits) && (nbits <= MAX_NUM_BITS));
    memset(num_tab_.min_tab_, 0xff, sizeof(num_tab_.min_tab_));
}

int64_t NumPool::GetNumber()
{
    int64_t ret = min_free_num_.GetValue();
    // check if any free numbers left
    if ((ret == max_num_) && (ret == max_num_)) {
        return -1;
    }
    // clear the bit in postion (inex, offset) 
    auto& index = min_free_num_.idx_;
    auto& offset = min_free_num_.off_;
    num_tab_.cur_tab_[index] &= (~(1u << (BIT_OFF_MASK - offset)));
    /****************************************************************/
    // update max_used_num_
    if (max_used_num_ < min_free_num_) {
        max_used_num_ = min_free_num_;
    }
    /****************************************************************
     *  update min_free_num_
     */
    while (cur_tab_size_ < max_tab_size_) {
        while (index < cur_tab_size_) {
            uint64_t num = num_tab_.cur_tab_[index];
            offset = (num & (num - 1ull));
            num = (offset ^ num);
            if (num) {
                // next free number found
                offset = 0;
                while((num <<= 1)) offset++;
                return ret;
            }
            // search next 64-bits
            index++;
        }
        /****************************************************************
         * expand current bit map
         */
        uint64_t* new_tab = new(std::nothrow) uint64_t[(cur_tab_size_ << 1u)];
        if (new_tab == nullptr) {
            break;
        }
        memset(new_tab, 0xff, (cur_tab_size_ << 1u) * sizeof(uint64_t));
        memcpy(new_tab, num_tab_.cur_tab_, cur_tab_size_);
        uint64_t* ptr = num_tab_.cur_tab_;
        num_tab_.cur_tab_ = new_tab;
        cur_tab_size_ <<= 1;
        if (cur_tab_size_ != MIN_TAB_SIZE) {
            delete[] ptr;
        }
        /****************************************************************/
    }
    /****************************************************************/
    // no free number left
    min_free_num_ = max_num_;
    max_used_num_ = max_num_;

    return ret;
}

bool NumPool::GetNumber(const uint32_t num)
{
    if (cur_tab_size_ == MIN_TAB_SIZE) {
        num_tab_.cur_tab_ = new(std::nothrow) uint64_t[max_tab_size_];
        if (num_tab_.cur_tab_ == nullptr) {
            return false;
        }
        memset(num_tab_.cur_tab_, 0xff, max_tab_size_ * sizeof(uint64_t));
    }
    auto ctx = NetContext::GetContext();
    if ((min_free_num_ == max_num_) && (max_used_num_ == max_num_)) {
        LOG_DEBUG(ctx, "no free numbers left");
        return false;
    }
    if (num >= max_num_) {
        LOG_DEBUG(ctx, "requested number out of range");
        return false;
    }
    BitPosition num_pos { num };
    uint64_t bits = num_tab_.cur_tab_[num_pos.idx_];
    bits = ((bits << num_pos.off_) >> BIT_OFF_MASK);
    if (bits == 0) {
        LOG_DEBUG(ctx,
            "requested number %u is used: idx = %u, off = %u, bits = %lu",
            num,
            num_pos.idx_,
            num_pos.off_,
            num_tab_.cur_tab_[num_pos.idx_]);
        return false;
    }
    num_tab_.cur_tab_[num_pos.idx_] &= bits;
    bool found { false };
    if (min_free_num_ == num_pos) {
        /****************************************************************
         *  update min_free_num_
         */
        auto& index = min_free_num_.idx_;
        auto& offset = min_free_num_.off_;
        while (cur_tab_size_ < max_tab_size_) {
            while (index < cur_tab_size_) {
                uint64_t num = num_tab_.cur_tab_[index];
                offset = (num & (num - 1ull));
                num = (offset ^ num);
                if (num) {
                    // next free number found
                    offset = 0;
                    while((num <<= 1)) offset++;
                    found = true;
                    break;
                }
                // search next 64-bits
                index++;
            }
            if (found) {
                break;
            }
            /****************************************************************
             * expand current bit map
             */
            uint64_t* new_tab = new(std::nothrow) uint64_t[(cur_tab_size_ << 1u)];
            if (new_tab == nullptr) {
                break;
            }
            memset(new_tab, 0xff, (cur_tab_size_ << 1u) * sizeof(uint64_t));
            memcpy(new_tab, num_tab_.cur_tab_, cur_tab_size_);
            uint64_t* ptr = num_tab_.cur_tab_;
            num_tab_.cur_tab_ = new_tab;
            cur_tab_size_ <<= 1;
            if (cur_tab_size_ != MIN_TAB_SIZE) {
                delete[] ptr;
            }
            /****************************************************************/
        }
        /****************************************************************/
    }
    if (max_used_num_ < num_pos) {
        max_used_num_ = num_pos;
    }
    // no free number left
    if (found == false) {
        min_free_num_ = max_num_;
        max_used_num_ = max_num_;
    }

    return bits;
}

void NumPool::PutNumber(const uint32_t num)
{
    if (num >= max_num_) {
        return;
    }
    BitPosition num_pos { num };
    // set the bit
    num_tab_.cur_tab_[num_pos.idx_] |= (1u << (BIT_OFF_MASK - num_pos.off_));
    // update min_free_num_
    if (num_pos < min_free_num_) {
        min_free_num_ = num_pos;
    }
    /****************************************************************
     * update max_used_num_
     */
    if (num_pos == max_used_num_) {
        auto& index = max_used_num_.idx_;
        auto& offset = max_used_num_.off_;
        while (index) {
            uint64_t num = ~num_tab_.cur_tab_[index];
            offset = (num & (num - 1));
            num = (offset ^ num);
            if (num) {
                // next used number found
                offset = 0;
                while((num <<= 1)) offset++;
                return;
            }
            // search next 64-bits
            index--;
        }
        uint64_t num = ~num_tab_.cur_tab_[index];
        offset = (num & (num - 1ull));
        num = (offset ^ num);
        if (num) {
            // next used number found
            offset = 0;
            while((num <<= 1)) offset++;
            return;
        }
    }

    // all numbers are free
    max_used_num_ = 0;
    min_free_num_ = 0;

    return;
}